package ClassicDataStructuresAndAlgorithms.ClassicLinkedListAlgorithms;

public class Solution25 {
    //定义这个函数：以K个一组，不断反转元素，返回新的head
    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode p = head;
        int count = k;
        //如果说顺利执行完，那么p指向第k+1个元素
        while(p!=null && count>0){
            p = p.next;
            count--;
        }

        //base case了属于是
        if (count > 0){
            //count大于0，说明剩下的结点小于K，不需要反转了
            return head;
        }

        ListNode left = head;
//        //right指向第K个元素
//        for (int i = 1; i < k; i++) {
//            right = right.next;
//        }

        ListNode newHead =  reverseKGroup(p,k);
        ListNode right = reverseN(head,k);
        left.next = newHead;

        return right;
    }

    //反转前N个元素，返回新的head
    private ListNode reverseN(ListNode head, int k) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode nxt = head.next;

        while(k > 0){
            cur.next = pre;
            pre = cur;
            cur = nxt;
            if (nxt!=null){
                nxt = nxt.next;
            }
            k--;
        }

        return pre;
    }
}
